package org.leetcode.middle.leetcode438;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {

    public List<Integer> findAnagrams2(String s, String p) {

        List<Integer> res = new ArrayList<>();

        if (s.length()<p.length()){
            return res;
        }

        char[] sArray = new char[26];
        char[] pArray = new char[26];

        for (int i = 0; i < p.length(); i++) {
            sArray[s.charAt(i) - 'a']++;
            pArray[p.charAt(i) - 'a']++;
        }

        if (Arrays.equals(sArray, pArray)) {
            res.add(0);
        }

        for (int i = 0; i < s.length() - p.length(); i++) {
            sArray[s.charAt(i) - 'a']--;
            sArray[s.charAt(i + p.length()) - 'a']++;

            if (Arrays.equals(sArray, pArray)) {
                res.add(i + 1);
            }
        }

        return res;
    }

    public List<Integer> findAnagrams(String s, String p) {

        int sLength = s.length();
        int pLength = p.length();

        List<Integer> res = new ArrayList<>();

        if (sLength < pLength) {
            return res;
        }

        int[] sCount = new int[26];
        int[] pCount = new int[26];

        for (int i = 0; i < pLength; i++) {
            sCount[s.charAt(i) - 'a']++;
            pCount[p.charAt(i) - 'a']++;
        }

        if (Arrays.equals(sCount, pCount)) {
            res.add(0);
        }

        for (int i = 0; i < sLength - pLength; i++) {
            sCount[s.charAt(i) - 'a']--;
            sCount[s.charAt(i + pLength) - 'a']++;

            if (Arrays.equals(sCount, pCount)) {
                res.add(i + 1);
            }
        }

        return res;
    }
}
